package com.base.mergesort;

import java.util.Arrays;


public class Main {
	
	public static void main(String[] args) {
		int[] nums = new int[] {1, 12, 11, 13, 5, 6, 7};
		System.out.println(Arrays.toString(nums));
		new MergeSort().sort(nums);
		System.out.println(Arrays.toString(nums));
	}
}

class MergeSort {
	
	void sort(int[] nums) {
		mergeSort(nums, 0, nums.length - 1);
	}
	
	void mergeSort(int[] nums, int begin, int end) {
		if (begin >= end) return;
		
		int mid = begin + (end - begin)/2;
		mergeSort(nums, begin, mid);
		mergeSort(nums, mid + 1, end);
		merge(nums, begin, mid, end);
	}
	
	void merge(int[]nums, int begin, int mid, int end) {
		int n = end - begin + 1;
		int[] tmp = new int[nums.length];
		
		for (int i = begin; i <= end; i ++) {
			tmp[i] = nums[i];
		}
		
		int i = begin, j = mid + 1;
		int cur = begin;
		while(i <= mid && j <= end) {
			if (tmp[i] < tmp[j]) {
				nums[cur++] = tmp[i++];
			} else {
				nums[cur++] = tmp[j++];
				j ++;
			}
		}
		while(j <= end) {
			nums[cur++] = tmp[j++];
		}
		while(i <= mid) {
			nums[cur++] = tmp[i++];
		}
		
	}
	
}
